/*
 * ============================================================================
 * 栈 (Stack) - C语言实现
 * ============================================================================
 * 
 * 【核心定义】
 * 栈是一种后进先出(LIFO - Last In First Out)的线性数据结构。
 * 只允许在一端（栈顶）进行插入和删除操作。
 * 
 * 【内存布局】
 * 数组实现:
 *   栈底 → [10] [20] [30] [40] ← 栈顶(top=3)
 *          0    1    2    3
 * 
 * 链表实现:
 *   top → [40|next] → [30|next] → [20|next] → [10|NULL]
 *        （栈顶）                              （栈底）
 * 
 * 【基本操作】
 * - push(x):  将元素x压入栈顶
 * - pop():    弹出栈顶元素
 * - peek():   查看栈顶元素但不弹出
 * - isEmpty(): 判断栈是否为空
 * 
 * 【时间复杂度】
 * - push:   O(1)
 * - pop:    O(1)
 * - peek:   O(1)
 * - search: O(n)
 * 
 * 【空间复杂度】O(n)
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// ============================================================================
// 方式1: 数组实现栈
// ============================================================================
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;  // 栈顶索引
} ArrayStack;

// 创建栈
ArrayStack* createArrayStack() {
    ArrayStack* stack = (ArrayStack*)malloc(sizeof(ArrayStack));
    stack->top = -1;  // 空栈时top为-1
    return stack;
}

// 判断栈是否为空
bool isEmpty(ArrayStack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
bool isFull(ArrayStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

// 压栈
void push(ArrayStack* stack, int value) {
    if (isFull(stack)) {
        printf("错误: 栈已满\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 弹栈
int pop(ArrayStack* stack) {
    if (isEmpty(stack)) {
        printf("错误: 栈为空\n");
        return -1;
    }
    return stack->data[stack->top--];
}

// 查看栈顶元素
int peek(ArrayStack* stack) {
    if (isEmpty(stack)) {
        printf("错误: 栈为空\n");
        return -1;
    }
    return stack->data[stack->top];
}

// 获取栈大小
int size(ArrayStack* stack) {
    return stack->top + 1;
}

// 打印栈
void printStack(ArrayStack* stack) {
    printf("栈底 → [");
    for (int i = 0; i <= stack->top; i++) {
        printf("%d", stack->data[i]);
        if (i < stack->top) printf(", ");
    }
    printf("] ← 栈顶\n");
}

// ============================================================================
// 方式2: 链表实现栈（动态栈）
// ============================================================================
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

typedef struct {
    StackNode* top;
    int count;
} LinkedStack;

// 创建链表栈
LinkedStack* createLinkedStack() {
    LinkedStack* stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    stack->top = NULL;
    stack->count = 0;
    return stack;
}

// 压栈（链表）
void pushLinked(LinkedStack* stack, int value) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
    stack->count++;
}

// 弹栈（链表）
int popLinked(LinkedStack* stack) {
    if (stack->top == NULL) {
        printf("错误: 栈为空\n");
        return -1;
    }
    StackNode* temp = stack->top;
    int value = temp->data;
    stack->top = stack->top->next;
    free(temp);
    stack->count--;
    return value;
}

// ============================================================================
// 应用场景1: 括号匹配检查
// ============================================================================
bool isMatchingPair(char opening, char closing) {
    return (opening == '(' && closing == ')') ||
           (opening == '[' && closing == ']') ||
           (opening == '{' && closing == '}');
}

bool checkBalancedParentheses(const char* expression) {
    ArrayStack* stack = createArrayStack();
    
    for (int i = 0; expression[i] != '\0'; i++) {
        char ch = expression[i];
        
        // 遇到左括号，压栈
        if (ch == '(' || ch == '[' || ch == '{') {
            push(stack, ch);
        }
        // 遇到右括号，检查匹配
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (isEmpty(stack)) {
                free(stack);
                return false;
            }
            char top = pop(stack);
            if (!isMatchingPair(top, ch)) {
                free(stack);
                return false;
            }
        }
    }
    
    bool result = isEmpty(stack);
    free(stack);
    return result;
}

void example_bracket_matching() {
    printf("\n=== 应用场景1: 括号匹配检查 ===\n");
    printf("场景: 编译器语法检查，验证括号配对\n\n");
    
    const char* test_cases[] = {
        "{[()]}",
        "{[(])}",
        "((()))",
        "({[}])"
    };

    for (int i = 0; i < 4; i++) {
        printf("  \"%s\" → %s\n", test_cases[i],
               checkBalancedParentheses(test_cases[i]) ? "匹配✓" : "不匹配✗");
    }
    printf("\n优势: LIFO特性完美匹配括号的嵌套关系\n");
}

// ============================================================================
// 应用场景2: 表达式求值（后缀表达式）
// ============================================================================
int evaluatePostfix(const char* expression) {
    ArrayStack* stack = createArrayStack();
    
    for (int i = 0; expression[i] != '\0'; i++) {
        char ch = expression[i];
        
        if (ch == ' ') continue;
        
        // 如果是数字，压栈
        if (ch >= '0' && ch <= '9') {
            push(stack, ch - '0');
        }
        // 如果是运算符，弹出两个操作数
        else {
            int operand2 = pop(stack);
            int operand1 = pop(stack);
            int result;
            
            switch (ch) {
                case '+': result = operand1 + operand2; break;
                case '-': result = operand1 - operand2; break;
                case '*': result = operand1 * operand2; break;
                case '/': result = operand1 / operand2; break;
                default: result = 0;
            }
            push(stack, result);
        }
    }
    
    int result = pop(stack);
    free(stack);
    return result;
}

void example_expression_evaluation() {
    printf("\n=== 应用场景2: 表达式求值 ===\n");
    printf("场景: 计算器实现，后缀表达式求值\n\n");
    
    const char* postfix = "5 3 + 2 *";  // (5+3)*2 = 16
    printf("  后缀表达式: %s\n", postfix);
    printf("  计算结果: %d\n", evaluatePostfix(postfix));
    printf("  原理: 使用栈保存操作数，遇到运算符就计算\n");
    printf("\n优势: 栈结构简化了表达式求值过程\n");
}

// ============================================================================
// 应用场景3: 函数调用栈模拟
// ============================================================================
void functionC() {
    printf("      执行 functionC()\n");
}

void functionB() {
    printf("    执行 functionB()\n");
    printf("      → 调用 functionC()\n");
    functionC();
    printf("      ← functionC() 返回\n");
}

void functionA() {
    printf("  执行 functionA()\n");
    printf("    → 调用 functionB()\n");
    functionB();
    printf("    ← functionB() 返回\n");
}

void example_call_stack() {
    printf("\n=== 应用场景3: 函数调用栈 ===\n");
    printf("场景: 程序运行时的函数调用管理\n\n");
    printf("调用链: main() → A() → B() → C()\n\n");
    
    printf("执行过程:\n");
    printf("  main() 开始\n");
    printf("  → 调用 functionA()\n");
    functionA();
    printf("  ← functionA() 返回\n");
    printf("  main() 结束\n");
    
    printf("\n调用栈变化:\n");
    printf("  [main]              压栈\n");
    printf("  [main][A]           A入栈\n");
    printf("  [main][A][B]        B入栈\n");
    printf("  [main][A][B][C]     C入栈\n");
    printf("  [main][A][B]        C出栈（返回）\n");
    printf("  [main][A]           B出栈（返回）\n");
    printf("  [main]              A出栈（返回）\n");
    printf("  []                  main结束\n");
    printf("\n优势: 自动管理函数返回地址和局部变量\n");
}

// ============================================================================
// 应用场景4: 浏览器后退功能
// ============================================================================
void example_browser_back() {
    printf("\n=== 应用场景4: 浏览器后退功能 ===\n");
    printf("场景: 记录浏览历史，支持后退操作\n\n");
    
    ArrayStack* history = createArrayStack();
    const char* pages[] = {"首页", "搜索页", "详情页", "支付页"};
    
    printf("浏览过程:\n");
    for (int i = 0; i < 4; i++) {
        push(history, i);
        printf("  访问: %s\n", pages[i]);
    }
    
    printf("\n后退操作:\n");
    for (int i = 0; i < 2; i++) {
        int pageIdx = pop(history);
        printf("  从 %s 后退\n", pages[pageIdx]);
    }
    
    printf("\n当前页面: %s\n", pages[peek(history)]);
    printf("\n优势: 栈的LIFO特性完美实现后退功能\n");
    
    free(history);
}

// ============================================================================
// 主函数 - 演示所有功能
// ============================================================================
int main() {
    printf("╔════════════════════════════════════════╗\n");
    printf("║   栈 (Stack) - C语言实现               ║\n");
    printf("╚════════════════════════════════════════╝\n");
    
    // 基本操作演示
    printf("\n--- 栈基本操作（数组实现）---\n");
    ArrayStack* stack = createArrayStack();
    
    printf("1. 压栈: 10, 20, 30, 40\n   ");
    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
    push(stack, 40);
    printStack(stack);
    
    printf("2. 查看栈顶元素: %d\n", peek(stack));
    
    printf("3. 弹出元素: %d\n", pop(stack));
    printf("   ");
    printStack(stack);
    
    printf("4. 当前栈大小: %d\n", size(stack));
    printf("5. 栈是否为空: %s\n", isEmpty(stack) ? "是" : "否");
    
    // 链表实现演示
    printf("\n--- 栈基本操作（链表实现）---\n");
    LinkedStack* linkedStack = createLinkedStack();
    pushLinked(linkedStack, 100);
    pushLinked(linkedStack, 200);
    pushLinked(linkedStack, 300);
    printf("压栈: 100, 200, 300\n");
    printf("弹出: %d\n", popLinked(linkedStack));
    printf("栈大小: %d\n", linkedStack->count);
    
    // 应用场景演示
    example_bracket_matching();
    example_expression_evaluation();
    example_call_stack();
    example_browser_back();
    
    // 优势与局限
    printf("\n╔════════════════════════════════════════╗\n");
    printf("║   优势与局限                           ║\n");
    printf("╚════════════════════════════════════════╝\n");
    printf("\n✅ 优势:\n");
    printf("  1. 所有操作都是O(1)时间复杂度\n");
    printf("  2. LIFO特性适合很多场景\n");
    printf("  3. 实现简单，效率高\n");
    printf("  4. 自动管理数据的进出顺序\n");
    
    printf("\n⚠️ 局限:\n");
    printf("  1. 只能访问栈顶元素\n");
    printf("  2. 数组实现有大小限制\n");
    printf("  3. 不支持随机访问\n");
    printf("  4. 搜索效率低（需要弹出）\n");

    printf("\n💡 最佳使用场景:\n");
    printf("  - 括号匹配、表达式求值\n");
    printf("  - 函数调用栈\n");
    printf("  - 浏览器后退/前进\n");
    printf("  - 撤销/重做功能\n");
    printf("  - 深度优先搜索(DFS)\n");
    
    printf("\n📊 两种实现对比:\n");
    printf("  数组实现: 连续内存，缓存友好，但大小固定\n");
    printf("  链表实现: 动态大小，无上限，但有指针开销\n");
    
    // 清理
    free(stack);
    while (linkedStack->top != NULL) {
        popLinked(linkedStack);
    }
    free(linkedStack);
    
    return 0;
}
